package com.lsa.letcode.the107.btLevelOrderTravII;

import java.util.ArrayList;
import java.util.List;

import com.lsa.letcode.common.TreeNode;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
    	List<List<Integer>> travs = new ArrayList<List<Integer>>();
    	if (root == null){
    		return travs;
    	}
    	int depth = maxDepthRec(root);
    	for (int i = depth; i > 0; --i) {
    		List<Integer> trav = new ArrayList<Integer>();
    		traverseLevel(i, 1, root, trav);
    		travs.add(trav);
		}
        return travs;
    }
    
    private void traverseLevel(int level, int currentLevel, TreeNode root, List<Integer> trav ) {
    	if (root != null){
    		if (level == currentLevel) {
    			trav.add(root.val);
    		}
    		else{
    			traverseLevel(level, currentLevel + 1, root.left, trav);
    			traverseLevel(level, currentLevel + 1, root.right, trav);
    		}
    	}
    }
    
    private int maxDepthRec(TreeNode root) {
		if (root == null) {
			return 0;
		} else {
			return 1 + Math.max(maxDepthRec(root.left), maxDepthRec(root.right));
		}
	}
}